Network devices that have more than one outgoing network interface and are processing Internet Protocol (IP) packets need to decide how outgoing packets are going to be assigned to each of the available network interfaces. Due to limitations in standard IP networks, it is not desirable to send a single packet out more than one interface. Therefore, for a given outgoing packet, the network device needs to assign this packet to one of the network interfaces, at which point the network interface will transmit this packet across the network to its destination. The process of assigning packets to network interfaces is referred to as packet scheduling or scheduling.
In many cases scheduling is done in a static manner. That is, if Interface A is available, all packets are sent via it. If, however, Interface A is no longer available all packets are sent via Interface B. For example, this is the default behavior of many multi-homed IP routers. This approach is used for a variety of reasons inherent in way that IP networks address and route packets. However, there exist systems where a more advanced scheduling algorithm can yield beneficial outcomes.
More advanced scheduling algorithms fall into one of two categories; scheduling on a per-packet basis; and scheduling on a per-flow basis. When scheduling on a per-packet basis, a scheduler decides how to assign a given packet to a network interface based upon how it assigned the previous packet. An example of a simple per-packet scheduling algorithm is a round robin approach. Thus each packet is scheduled over a subsequent interface. These scheduling algorithms work best in environments where the network characteristics of each link are very similar, since network interfaces with different network characteristics can introduce packet reordering into a flow, which may be detrimental to the behavior of many flows.
Scheduling on a per-flow bases attempts to avoid this pitfall by operating on packets based on the flow to which they belong, and schedule packets from each flow over a common interface. In a per-flow scheduler, each flow is assigned to a single interface, but all interfaces can be in use at once if multiple flows are present in the system. An example of a simple per-flow scheduling algorithm is a round robin algorithm. However, the round robin algorithm is used to assign entire flows to a corresponding interface, and not individual packets. Once a flow is assigned to an interface, all the packets associated with that flow are routed over the assigned interface.
In order to manage multiple flows, a table is created to map each flow to the interface to which it is assigned. This ensures that subsequent packets will be scheduled over the proper interface. However, a table-based approach has several disadvantages. First, it is necessary to expire entries from the table, which is not a trivial exercise for stateless flows like User Data Protocol (UDP) flows. Second, it is necessary to access the table every time a packet arrives, which can be an inefficient operation for large tables or a highly complex implementation if more efficient data structures are used. Third, this approach requires that the amount of data stored be based upon the number of flows, which can grow quite large as clients make large numbers of connections. On a server, having large tables like this for each client may be highly inefficient or prohibitively expensive.
Yet further, some network systems require packet scheduling to be performed by two devices working together across a network link. For example, in a multi-interface encapsulation system, it may be necessary for both a client component and a server component to perform packet scheduling when sending packets across the encapsulation system to their destination. In such environments, it is desirable for both the client and server to be making the same scheduling decisions, to avoid the traffic sent in one direction be subject to different network conditions than traffic being sent in the other direction. For example, if a Transmission Control Protocol (TCP) stream is scheduled across a high speed, low latency interface but the acknowledgements are scheduled across a high-latency interface, then the TCP stream will throttle itself unnecessarily because TCP will incorrectly interpret the slow acknowledgments as a slow network. Thus, in order to ensure that both the client and server are scheduling packets across the same network link, the table needs to be maintained by both devices. Further, synchronization data needs to be sent between the devices for each new flow, increasing the bandwidth overhead.
Accordingly, it is desirable to implement a scheduling algorithm that reduces the system overhead required for current implementations.